翻訳と辞書
Words near each other
・ Switzerland at the 2015 European Games
・ Switzerland at the 2015 Summer Universiade
・ Switzerland at the 2015 UCI Road World Championships
・ Switchfoot discography
・ Switchfootage
・ Switchgear
・ Switchin' Kitten
・ Switching
・ Switching (film)
・ Switching and terminal railroad
・ Switching barriers
・ Switching Channels
・ Switching circuit theory
・ Switching Control Center System
・ Switching Goals
Switching lemma
・ Switching loop
・ Switching station
・ Switching time
・ Switchman
・ Switchmas
・ Switchmen's Union of North America
・ Switchover
・ Switchover Media
・ Switchstance
・ Switchstance (album)
・ SwitchUp
・ Switchwise
・ Switchyard
・ Switchyard reactor


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Switching lemma : ウィキペディア英語版
Switching lemma
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.
Using the switching lemma, showed that Boolean circuits of depth ''k'' in which only AND, OR, and NOT logic gates are allowed require size
: \exp\left(\Omega\left(n^}\right)\right)
for computing the parity function.
The switching lemma says that depth-2 circuits in which some fraction of the variables have been set randomly depend with high probability only on very few variables after the restriction. The name of the switching lemma stems from the following observation: Take an arbitrary formula in conjunctive normal form, which is in particular a depth-2 circuit. Now the switching lemma guarantees that after setting some variables randomly, we end up with a Boolean function that depends only on few variables, i.e., it can be computed by a decision tree of some small depth d. This allows us to write the restricted function as a small formula in disjunctive normal form. A formula in conjunctive normal form hit by a random restriction of the variables can therefore be "switched" to a small formula in disjunctive normal form.
The original proof of the switching lemma involves an argument with conditional probabilities.
Arguably simpler proofs have been subsequently given by and . For an introduction, see Chapter 14 in .
== References ==

*
*
*
*


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Switching lemma」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.